#include <iostream>
#include <cstring>
#include <string>

using namespace std;

typedef long long int64;

int	main()
{
	int T;
	cin >> T;

	int a[400], b[400];
	int n, m;
	while (T--)
	{
		cin >> n >> m;
		for (int i = 0; i < m; ++i) cin >> a[i] >> b[i];
		int answer = m;
		for (int s = 0; s < (1 << (n - 1)); ++s)
		{
			int cost = 0;
			for (int i = 0; i < m && cost < answer; ++i)
				if (!(s & (1 << a[i])) ^ !(s & (1 << b[i])) ^ 1)
					++cost;
			if (cost < answer) answer = cost;
		}
		cout << answer << endl;
	}
	return 0;
}